#pragma warning(disable:4996)
#pragma warning(disable:6031)

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//int _QuickSort(int* arr, int left, int right)
//{
//	int keyi = left++;
//	while (left <= right)
//	{
//		while (left <= right && arr[right] > arr[keyi])
//		{
//			right--;
//		}
//		while (left <= right && arr[left] < arr[keyi])
//		{
//			left++;
//		}
//		if (left <= right)
//		{
//			Swap(&arr[left++], &arr[right--]);
//		}
//	}
//	Swap(&arr[keyi], &arr[right]);
//	return right;
//}

//int _QuickSort(int* arr, int left, int right)
//{
//	int hole = left;
//	int key = arr[hole];
//	while (left < right)
//	{
//		while (left < right && arr[right] >= key)
//		{
//			right--;
//		}
//		arr[hole] = arr[right];
//		hole = right;
//		while (left < right && arr[left] <= key)
//		{
//			left++;
//		}
//		arr[hole] = arr[left];
//		hole = left;
//	}
//	arr[hole] = key;
//	return hole;
//}

//int _QuickSort(int* arr, int left, int right)
//{
//	int prev = left;
//	int cur = left + 1;
//	while (cur <= right)
//	{
//		if (arr[cur] < arr[left] && ++prev != cur)
//		{
//			Swap(&arr[prev], &arr[cur]);
//		}
//		cur++;
//	}
//	Swap(&arr[left], &arr[prev]);
//	return prev;
//}
//
//void QuickSort(int* arr, int left, int right)
//{
//	if (left >= right)
//	{
//		return;
//	}
//	int key = _QuickSort(arr, left, right);
//	QuickSort(arr, left, key - 1);
//	QuickSort(arr, key + 1, right);;
//}

//void _MergeSort(int* arr, int left, int right, int* tmp)
//{
//	if (left >= right)
//	{
//		return;
//	}
//	int mid = (right + left) / 2;
//	_MergeSort(arr, left, mid, tmp);
//	_MergeSort(arr, mid+1, right, tmp);
//	int begin1 = left, end1 = mid;
//	int begin2 = mid+1, end2 = right;
//	int index = begin1;
//	while (begin1 <= end1 && begin2 <= end2)
//	{
//		if (arr[begin1] < arr[begin2])
//		{
//			tmp[index++] = arr[begin1++];
//		}
//		else
//		{
//			tmp[index++] = arr[begin2++];
//		}
//	}
//	while (begin1 <= end1)
//	{
//		tmp[index++] = arr[begin1++];
//	}
//	while (begin2 <= end2)
//	{
//		tmp[index++] = arr[begin2++];
//	}
//	for (int i = left; i <= right; i++)
//	{
//		arr[i] = tmp[i];
//	}
//}
//
//void MergeSort(int* arr, int n)
//{
//	int* tmp = (int*)malloc(n * sizeof(int));
//	if (tmp == NULL)
//	{
//		exit(1);
//	}
//	_MergeSort(arr, 0, n - 1, tmp);
//	free(tmp);
//	tmp = NULL;
//}

void CountSort(int* arr, int n)
{
	int max = arr[0];
	int min = arr[0];
	for (int i = 0; i < n; i++)
	{
		if (arr[i] > max)
		{
			max = arr[i];
		}
		if (arr[i] < min)
		{
			min = arr[i];
		}
	}
	int range = max - min + 1;
	int* count = (int*)malloc(range * sizeof(int));
	if (count == NULL)
	{
		exit(1);
	}
	memset(count, 0, range * sizeof(int));
	for (int i = 0; i < n; i++)
	{
		count[arr[i] - min]++;
	}
	int index = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			arr[index++] = i + min;
		}
	}
	free(count);
}

int main()
{
	int arr[] = { 5,4,1,3,6,9,7,2,8,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	//QuickSort(arr, 0, sz - 1);
	/*MergeSort(arr, sz);*/
	CountSort(arr, sz);
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}